package LeetCode.leetcode;

/**
 * leetCode35
 * 查找有序数组中的值，若不存在，返回插入后位置的index
 * @author: leiwenkang02@meituan.com
 * @date: 2018/7/31
 * @time: 21:00
 */
public class Test35搜索插入位置 {
    public static void main(String[] args) {
        int[] nums = {31,2,5,6,12,10,9};
        System.out.println(searchInsert(nums, 8));
    }
    //二分
    public static int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int mid = (low+high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid-1;
            } else {
                low = mid +1;
            }
        }
        return low;
    }

    //快排
    public static int searchInsert2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int[] array = new int[nums.length + 1];
        int i = 0;
        array[0] = target;
        while (i < nums.length) {
            array[i + 1] = nums[i];
            i++;
        }
        return partition(array);

    }

    public static int partition(int[] array) {
        int val = array[0];
        int start = 0;
        int end = array.length - 1;
        while (start < end) {
            while (start < end && array[end] >= val) {
               end--;
            }
            array[start] = array[end];
            while (start < end && array[start] <= val) {
                start++;
            }
            array[end] = array[start];
        }
        return start;
    }
}
